题目分析

加油站是经典的贪心问题，代码量很少，但是思路非常灵活，小伙伴们先尝试能否求解。

贪心

贪心算法代码量非常少，但是证明难度非常大，这道题更是不容易理解。小伙伴们要清楚一件事情，如果油的总数大于等于走完所有路径所需要的油量，一定能够找到一个合适的起点。最后走的点一定是花费大于等于提供油量的点，如果提供的油量大于花费量，我们可以将起点提前，这样是一种更好的解法。如gas = [1, 3, 5], cost = [3, 2, 4]。这时如果选择2号为起点，走到0号还剩1升油，不够，而且发现终点1号位置的提供油量大于花费，所以可以将起点从2号提前到1号，从1号加油站出发。

因此贪心的目的是尽可能在前期多保存油量，操作是要从提供多，消耗少的加油站出发。可以根据提供和消耗算出累积的油量，也就是说要让累积越多越好。也就是让累积为负的放在最后。所以我们找出累积最小值作为结束的加油站编号。

**不妨设k是累积最小值，则k + 1作为起点编号。

k + 1的提供量一定大于等于消耗量，因为k是累积的最小值，如果k + 1的提供小于消耗，则k + 1的净增加是负数，那么累积的最小值是k + 1，与条件矛盾，所以这时将k + 2作为起点不如将k + 1作为起点。
k的提供量一定小于消耗量，因为k是累积的最小值，如果k的提供大于等于消耗，则k的净增加是非数，那么累积的最小值是k - 1，与条件矛盾，所以这时将k作为起点不如将k + 1作为起点**。
k + 2作为起点的分析同k + 1，k - 1作为起点的分析同k，这个思路非常难以理解，仔细想想好像有道理，但是又很难证明。

因此要找出累积的最小值即可，然后加1可得出发编号。这里直接给出代码，算法的时间复杂度为$O(n)，空间复杂度为$O(1)$

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        current, mini_idx, mini_val = 0, 0, float('inf')
        for i in range(len(gas)):
            current += gas[i] - cost[i]
            if current < mini_val:
                mini_val, mini_idx = current, i
        return -1 if current < 0 else (mini_idx + 1) % len(gas)

数学

数学方法相对容易理解，不理解上面思路的小伙伴们可以掌握这种算法。

这个算法模拟开车过程，i为出发加油站的编号，i从0开始索引到最后一个站点，j为当前到达的站点，remain为当前油量，当remain < 0时，说明无法到达，此时i = j + 1，这一步是这个算法的精华。如果i += 1则相当于遍历所有的情况，时间复杂度为$O(n^2)$，而i = j + 1大大减少了时间复杂度，相当于i和j共用一层循环。

这句话如何理解呢？如果从i出发，最多只能到达j站台，那么中间这些站点都没必要进行尝试，假设中间的站点为k，从i到k是满足条件的，说明在k时，remain大于等于0，但是从k到j无法到达。那么从k出发时，如果remain等于0，那么必定也无法到达j的位置，因此不需要模拟站台k，可以直接从j + 1站台开始继续模拟。这个算法的时间复杂度为$O(n)，空间复杂度为$O(1)$

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        i, lens = 0, len(gas)
        while i < lens:
            j = i
            remain = gas[i] - cost[i]
            while remain >= 0:
                j += 1
                if j - i == lens:
                   return i
                remain += gas[j % lens] - cost[j % lens]
            i = j + 1
        return -1

刷题总结

这个题目短小而精悍，看似非常简单，但是做起来却非常困难，小伙伴没有没有感受到这个题目的精妙之处。